//给定一个未排序的整数数组，找出其中没有出现的最小的正整数。 
//
// 示例 1: 
//
// 输入: [1,2,0]
//输出: 3
// 
//
// 示例 2: 
//
// 输入: [3,4,-1,1]
//输出: 2
// 
//
// 示例 3: 
//
// 输入: [7,8,9,11,12]
//输出: 1
// 
//
// 说明: 
//
// 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。 
// Related Topics 数组

  
package com.gule.gl.leetcode.editor.cn;

import java.util.Objects;
/**
 * 桶的思想 + 抽屉原理
 * @link https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
 * 1、数字 i 落在“区间范围里”；
 *
 * 例如：[3, 4, -1, 1]，一共 4 个数字，那么如果这个数组中出现 “1”、“2”、“3”、“4”，就是我们重点要关注的数字了；
 * 又例如：[7, 8, 9, 11, 12] 一共 5 个数字，每一个都不是 “1”、“2”、“3”、“4”、“5” 中的一个，因此我们无须关注它们；
 *
 * 2、i 就应该放在索引为i - 1 的位置上；
 *
 * 这句话也可以这么说 “索引为 i 的位置上应该存放的数字是 i + 1”。
 *
 * 就看上面那张图，数字 11 应该放在索引为 00 的位置上，数字 33 应该放在索引为 22 的位置上，数字 44 应该放在索引为 33 的位置上。一个数字放在它应该放的位置上，我们就认为这个位置是“和谐”的，看起来“顺眼”的。
 *
 * 按照以上规则排好序以后，缺失的第 11 个正数一下子就看出来了，那么“最不和谐”的数字的索引 + 1+1，就为所求。那如果所有的数字都“和谐”，数组的长度 + 1+1 就为所求。
 *
 * 作者：liweiwei1419
 * 链接：https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @param
 * @return
 */
public class FirstMissingPositive{
    public static void main(String[] args) {
         Solution solution = new FirstMissingPositive().new Solution();
         int[] test = {1,2,0};
         System.out.println(solution.firstMissingPositive(test));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //桶的思想 + 抽屉原理
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1) {
                if (nums[i] <= 0 || nums[i] > nums.length || nums[i] == nums[nums[i] - 1]) {
                    break;
                }
                // 将nums[i] 放置到对应位置上[1,2,3...]
                //交换对应的位置
                int idx = nums[i] - 1;
                nums[i] = nums[idx];
                nums[idx] = idx + 1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != (i + 1)) {
                return (i + 1);
            }
        }
        return (nums.length + 1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
